package sort;

import java.util.Arrays;
import java.util.Random;

/**
 * 本次跟着老师采用了逐步求解的办法，希尔排序最牛逼的点就在于步长.
 *      length / 2 得到每次步长，如果是奇数数组 arr = {8,9,1,7,2} 也是分成2组 [8,1,2] 和 [9,7]
 *      参考了  https://blog.csdn.net/Websphere_zxf/article/details/109013001
 *
 *      希尔排序花费 : 0.023s . 太nb了
 *
 *      Just remember 希尔排序在插入排序的基础上增加了分组。同一组内还是插入排序
 */
public class ShellSorting {
    public static void main(String[] args) {
        int []arr = {8,9,1,7,2,3,5,4,6,10,9};
        int []arr2 = {8,9,1,7,2};
        shellRound1(arr);
        System.out.println(Arrays.toString(arr));
        shellRound2(arr);
        System.out.println(Arrays.toString(arr));
        shellRound3(arr);
        System.out.println(Arrays.toString(arr));
        shellSort(arr2);
        System.out.println(Arrays.toString(arr2));
        //costTime();

    }
    // 第一轮排序 , 10 /2 = 5 分成5组。步长为5
    public static void shellRound1(int [] array){
        int temp = 0;
        int index = 0;
        int length = array.length;
        for (int i = 5; i <length; i++) {
           temp = array[i];
           index = i-5;
           while (index>=0 && temp <array[index]){
               array[index+5] = array[index];
               index -= 5;
           }
           array[index+5] = temp;
        }
    }
    // 第二轮排序，5 / 2 = 2 步长为2
    public static void shellRound2(int []array){
        int temp = 0;
        int index = 0;
        int length = array.length;
        for (int i = 2; i <length; i++) {
            // for循环里面就是插入排序的逻辑
            temp = array[i];
            index = i-2;
            while (index>=0 && temp<array[index]){
                array[index+2] = array[index];
                index -=2;
            }
            array[index+2] = temp;

        }
    }
    // 第三组排序  2 / 2 =1 步长为1
    public static void shellRound3(int []array){
        int temp = 0;
        int index = 0;
        int length = array.length;
        for (int i = 1; i <= length-1; i++) {
            temp = array[i];
            index = i-1;
            while (index>=0 && temp<array[index]){
                array[index+1] = array[index];
                index-=1;
            }
            array[index+1] = temp;
        }
    }
    // 总体代码实现
    public static void shellSort(int []array){
        int insertVal = 0;
        int index = 0;
        int length = array.length;
        // 步长
        int gap = length/2;
        while (gap >0){
            for (int i = gap; i < length; i++) {
                insertVal = array[i];
                index = i - gap;
                while (index>=0 && insertVal<array[index]){
                    array[index+gap] = array[index];
                    index-=gap;
                }
                array[index+gap] =insertVal;
            }
            gap /=2;
        }
    }
    /**
     *  测试八万的数据
     */
    public static void costTime() {
        int[] arrays3 = new int[80000];
        Random random2 = new Random();
        for (int i = 0; i < arrays3.length; i++) {
            arrays3[i] = random2.nextInt(80000);
        }
        long startTime = System.currentTimeMillis();
        shellSort(arrays3);   // 正规的插入，有值的后移
        long endTime = System.currentTimeMillis();
        System.out.println("程序运行时间优化时间为：" + (endTime - startTime)*0.001 + "s"); //输出程序运行时间
    }
}
